package com.ttx.algorithm.leetcode.usual;

import cn.hutool.core.lang.Assert;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/my-calendar-ii/
 *
 * 731. 我的日程安排表 II
 *
 * 实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。
 *
 * MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，  start <= x < end。
 *
 * 当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。
 *
 * 每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。
 *
 * 请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
 *
 * 示例：
 *
 * MyCalendar();
 * MyCalendar.book(10, 20); // returns true
 * MyCalendar.book(50, 60); // returns true
 * MyCalendar.book(10, 40); // returns true
 * MyCalendar.book(5, 15); // returns false
 * MyCalendar.book(5, 10); // returns true
 * MyCalendar.book(25, 55); // returns true
 * 解释：
 * 前两个日程安排可以添加至日历中。 第三个日程安排会导致双重预订，但可以添加至日历中。
 * 第四个日程安排活动（5,15）不能添加至日历中，因为它会导致三重预订。
 * 第五个日程安排（5,10）可以添加至日历中，因为它未使用已经双重预订的时间10。
 * 第六个日程安排（25,55）可以添加至日历中，因为时间 [25,40] 将和第三个日程安排双重预订；
 * 时间 [40,50] 将单独预订，时间 [50,55）将和第二个日程安排双重预订。
 *
 *
 *
 * 提示：
 *
 *     每个测试用例，调用 MyCalendar.book 函数最多不超过 1000次。
 *     调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。
 *
 * @author TimFruit
 * @date 20-5-5 上午10:47
 */
public class P731MyCalendar2 {
    public static void main(String[] args) {

        MyCalendarTwo myCalendar=new MyCalendarTwo();

//        String paramString="[[10,20],[50,60],[10,40],[5,15],[5,10],[25,55]]";
//        String expectedResult="[true,true,true,false,true,true]";

//        String paramString="[[24,40],[43,50],[27,43],[5,21],[30,40],[14,29],[3,19],[3,14],[25,39],[6,19]]";
//        String expectedResult="[true,true,true,true,false,false,true,false,false,false]";



//        String paramString="[[36,41],[28,34],[40,46],[10,18],[4,11],[25,34],[36,44],[32,40],[34,39],[40,49]]";
//        String expectedResult="";

//
//        String paramString="[[97,100],[51,65],[27,46],[90,100],[20,32],[15,28],[60,73],[77,91],[67,85],[58,72],[74,93],[73,83],[71,87],[97,100],[14,31],[26,37],[66,76],[52,67],[24,43],[6,23],[94,100],[33,44],[30,46],[6,20],[71,87],[49,59],[38,55],[4,17],[46,61],[13,31],[94,100],[47,65],[9,25],[4,20],[2,17],[28,42],[26,38],[72,83],[43,61],[18,35]]";
//        String expectedResult="";

        String paramString="[[89,100],[30,43],[92,100],[31,49],[59,76],[60,73],[31,49],[80,99],[48,60],[36,52],[67,82],[96,100],[22,35],[18,32],[9,24],[11,27],[94,100],[12,22],[61,74],[3,20],[14,28],[27,37],[5,20],[1,11],[96,100],[33,44],[90,100],[40,54],[23,35],[18,32],[78,89],[56,66],[83,93],[45,59],[40,59],[94,100],[99,100],[86,96],[43,61],[29,45],[21,36],[13,31],[17,30],[16,30],[80,94],[38,50],[15,30],[62,79],[25,39],[73,85],[39,56],[80,97],[42,57],[32,47],[59,78],[35,53],[56,74],[75,85],[39,54],[63,82]]";
        String expectedResult="[true,true,true,true,true,true,false,false,true,false,false,false,false,false,true,true,false,false,false,false,false,false,false,true,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false]";







        List<Boolean> resultList=new ArrayList<>();

        List<Integer> params=param(paramString);

        System.out.println(params);


        for(int i=0;i<params.size();i+=2){
            boolean re=myCalendar.book(params.get(i), params.get(i+1));
            resultList.add(re);
        }



        String resultString=resultList.toString().replace(" ","");
        System.out.println(resultString);
        Assert.state(expectedResult.equals(resultString));


    }

    private static List<Integer> param(String paramString){
        // [[],[47,50],[33,41],[39,45],[33,42],[25,32],[26,35],[19,25],[3,8],[8,13],[18,27]]
        paramString=paramString.replace("[","").replace("]","");
        String[] strs=paramString.split(",");

        List<Integer> list=new ArrayList<>();
        String key=null;
        String value=null;
        int i=0;
        for(;i<strs.length;i++){


            list.add(Integer.valueOf(strs[i]));

        }

        return list;
    }








    static     class MyCalendarTwo {

        // [start, end)
        TreeMap<Integer,Integer> planTree=new TreeMap<>();
        // start, count
        TreeMap<Integer,Integer> countTree=new TreeMap<>();

        Map.Entry<Integer, Integer> firstEntry =null;
        Map.Entry<Integer, Integer> secondEntry =null;
        Map.Entry<Integer, Integer> tempEntry =null;



        boolean couldBook=false;

        int limitCount=2;
        int tempCount;
        int tempStart;

        public MyCalendarTwo() {
            // start 和 end 的取值范围为 [0, 10^9]
            planTree.put(-2, -1);
            planTree.put(Integer.MAX_VALUE-1,Integer.MAX_VALUE);

            countTree.put(-2, 0);
            countTree.put(Integer.MAX_VALUE-1, 0);
        }

        public boolean book(int start, int end) {


            couldBook=false;

            //<=
            firstEntry=planTree.floorEntry(start);

            //>=
            secondEntry=planTree.ceilingEntry(start);


            // firstEntry.key <= start <= secondEntry.key

            if(couldBookWithFirstEntry(firstEntry, start) && couldBookWithSecondEntry(secondEntry, end)){

                if(firstEntry.getValue() <= start && end <= secondEntry.getKey()){
                    planTree.put(start, end);
                    countTree.put(start, 1);
                    return true;
                }


                // 可重复部分
                tempStart=start;
                if(firstEntry.getValue()> tempStart){

                    //将firstEntry线段分成两部分，
                    if(firstEntry.getKey() < tempStart){ // 前一部分非重复
                        planTree.put(firstEntry.getKey(), tempStart);
                    }


                    //后一部分重复
                    tempCount=countTree.get(firstEntry.getKey());
                    if(end<=firstEntry.getValue()){
                        planTree.put(tempStart, end);
                        countTree.put(tempStart, tempCount+1);

                        if(end<firstEntry.getValue()){
                            planTree.put(end,firstEntry.getValue());
                            countTree.put(end, tempCount);
                        }
                        return true;
                    }else {
                        planTree.put(tempStart, firstEntry.getValue());
                        countTree.put(tempStart,tempCount+1);
                        tempStart=firstEntry.getValue();
                    }

                }





                while(secondEntry.getValue() < end){

                    if(tempStart<secondEntry.getKey()){
                        planTree.put(tempStart, secondEntry.getKey());
                        countTree.put(tempStart, 1);
                    }

                    tempCount=countTree.get(secondEntry.getKey());
                    planTree.put(secondEntry.getKey(), secondEntry.getValue());
                    countTree.put(secondEntry.getKey(), tempCount+1);


                    tempStart=secondEntry.getValue();
                    secondEntry=planTree.ceilingEntry(secondEntry.getValue());

                }

                if(end <= secondEntry.getKey()){
                    planTree.put(tempStart, end);
                    countTree.put(tempStart, 1);
                }else {
                    if(tempStart < secondEntry.getKey()){
                        planTree.put(tempStart, secondEntry.getKey());
                        countTree.put(tempStart, 1);
                    }


                    tempCount=countTree.get(secondEntry.getKey());
                    planTree.put(secondEntry.getKey(), end);
                    countTree.put(secondEntry.getKey(), tempCount+1);

                    if(end<secondEntry.getValue()){
                        planTree.put(end, secondEntry.getValue());
                        countTree.put(end, tempCount);
                    }
                }


                return true;

            }

            return false;
        }



        private boolean couldBookWithFirstEntry(Map.Entry<Integer, Integer> _firstEntry , int toStart){
            if(_firstEntry.getValue()<=toStart){
                return true;
            }
            Integer count=countTree.get(_firstEntry.getKey());
            if(count<limitCount){
                return true;
            }
            return false;
        }


        private boolean couldBookWithSecondEntry(Map.Entry<Integer, Integer> _secondEntry , int toEnd){

            if(_secondEntry.getKey()>=toEnd){
                return true;
            }

            while(_secondEntry.getValue() < toEnd && countTree.get(_secondEntry.getKey())<limitCount){
                _secondEntry=planTree.ceilingEntry(_secondEntry.getValue());
            }


            if(_secondEntry.getKey()>=toEnd){
                return true;
            }

            Integer count=countTree.get(_secondEntry.getKey());
            if(count<limitCount){
                return true;
            }
            return false;
        }


    }





}